package com.vincent.exam.tree;

import java.util.ArrayList;

/**
 * 层序遍历
 */
public class LevelOrder {
    private ArrayList<ArrayList<Integer>> result = new ArrayList<>();

    /**
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList <>>
     */
    public ArrayList<ArrayList<Integer>> order(TreeNode root) {
        // write code here
        if (root == null) {
            return result;
        }
        count(root, 0);
        return result;
    }

    public void count(TreeNode root, int level) {
        // 第一次层数等于结果集合大小时添加一个list
        if (result.size() == level) {
            result.add(new ArrayList<Integer>());
        }
        // 添加当节点的值
        ArrayList<Integer> list = result.get(level);
        list.add(root.val);
        // 递归，先左后右
        if (root.left != null) {
            count(root.left, level + 1);
        }
        if (root.right != null) {
            count(root.right, level + 1);
        }
    }
}
